# math_utils.py
import random
import hashlib

# 扩展欧几里得算法求模逆
def extended_gcd(a, b):
    """
    扩展欧几里得算法
    返回 (gcd, x, y) 使得 ax + by = gcd
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = extended_gcd(b % a, a)
        return g, y - (b // a) * x, x

def modInverse(a, m):
    """
    计算 a 在模 m 下的乘法逆元
    即找到 x 使得 (a * x) % m == 1
    """
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('模逆元不存在')
    else:
        return x % m

# Miller-Rabin 素性检验
def is_prime(n, k=10): # k 是测试次数，次数越多，准确性越高
    """
    Miller-Rabin 素性检验算法
    :param n: 待检验的数
    :param k: 测试的轮数，一般取5到10即可有很高的正确率
    :return: 如果n可能是素数则返回True，否则返回False
    """
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False

    # 将 n-1 表示为 2^s * d，其中 d 是奇数
    s = 0
    d = n - 1
    while d % 2 == 0:
        d //= 2
        s += 1

    for _ in range(k):
        a = random.randrange(2, n - 1) # 随机选择一个 witness
        x = pow(a, d, n) # 计算 a^d mod n

        if x == 1 or x == n - 1:
            continue # 可能是一个素数，继续下一轮测试

        # 进行 s-1 次平方测试
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break # 可能是一个素数，跳出内层循环，继续外层 witness 测试
        else:
            # 如果内层循环正常结束（即没有break），说明没有找到 x = n-1
            # 并且最初的 x != 1 且 x != n-1，所以 n 是合数
            return False
    return True # 通过了所有测试，n 极有可能是素数

def generate_prime_candidate(length):
    """
    生成一个指定长度的奇数作为素数候选者
    :param length: 二进制位数
    :return: 一个奇数
    """
    # 生成一个 length 位的随机数
    p = random.getrandbits(length)
    # 设置最高位和最低位为1，确保其长度和为奇数
    p |= (1 << length - 1) | 1
    return p

def generate_large_prime(length=256):
    """
    生成一个指定长度的大素数
    :param length: 素数的二进制位数 (例如为ECC F_p生成256位, 为RSA生成1024, 2048, 2024等)
    :return: 一个大素数
    """
    print(f"开始生成 {length} 位的大素数...")
    p = 4
    # 持续生成候选者并测试，直到找到素数
    count = 0
    while not is_prime(p, k=20): # 对大素数增加测试轮数
        count +=1
        if count % 10 == 0:
            print(f"  已尝试 {count} 个候选数...")
        p = generate_prime_candidate(length)
    print(f"成功生成 {length} 位素数 (尝试了 {count+1} 个候选数).")
    return p

# if __name__ == '__main__':
#     print("测试数学工具模块:")
#     # 测试模逆元
#     a = 17
#     m = 3120
#     try:
#         inv_a = modInverse(a, m)
#         print(f"{a} 模 {m} 的逆元是: {inv_a}")
#         print(f"验证: ({a} * {inv_a}) % {m} = {(a * inv_a) % m}")
#     except Exception as e:
#         print(e)

#     # 测试素性检验
#     num1 = 29
#     num2 = 30
#     print(f"{num1} 是素数吗? {is_prime(num1)}")
#     print(f"{num2} 是素数吗? {is_prime(num2)}")
    
#     # 生成一个较小的素数用于测试
#     small_prime = generate_large_prime(16) # 生成一个16位的素数
#     print(f"生成的16位素数: {small_prime}")

#     # 生成一个ECC常用的256位素数 (这可能需要一些时间)
#     # prime_256 = generate_large_prime(256)
#     # print(f"生成的256位素数: {prime_256}")

#     # 按您的要求，生成一个2024位素数 (这会非常耗时，几分钟到几十分钟甚至更久，取决于CPU)
#     # prime_2024 = generate_large_prime(2024)
#     # print(f"生成的2024位素数: {prime_2024}")
#     # print("注意：2024位素数主要用于RSA等算法，ECC通常使用更小的素数（如256位）定义其有限域。")
    
    